МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОБЛАСТНОЙ УНИВЕРСИТЕТ

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра прикладной математики и информатики

КУРСОВАЯ РАБОТА по дисциплине

«ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ»

Тема: «Разработка модели и решение задачи линейного программирования (на примере задачи о выборе оптимальных проектов для финансирования)»

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5

1.1. Общая математическая формулировка задачи линейного программирования……5

1.2. Методы решения задачи линейного программирования……7

2. РАЗРАБОТКА МОДЕЛИ И РЕШЕНИЕ ЗАДАЧИ О ВЫБОРЕ ОПТИМАЛЬНЫХ ПРОЕКТОВ ДЛЯ ФИНАНСИРОВАНИЯ 15

2.1. Вербальная постановка задачи о выборе оптимальных проектов для финансирования.15

2.2. Разработка экономико-математической модели задачи о выборе оптимальных проектов для финансирования….…15

2.3. Решение поставленной задачи симплекс-методом……17

2.4. Решение поставленной задачи с помощью средств EXСEL (надстройка «Поиск решения»)….19

2.5. Интерпретация результатов расчетов и выработка управленческого решения…………28

ЗАКЛЮЧЕНИЕ 29

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 31

Внимание!

Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №3495, цена оригинала 1000 рублей. Оформлена в программе Microsoft Word.

Оплата. Контакты.

ВВЕДЕНИЕ

При выполнении любых действий и при принятии решений в различных областях деятельности основополагающим желанием является получение наилучшего результата. Смысл действий и принятие решений определяются за¬интересованностью в этих действиях и решениях в соответствии с имеющимися возможностями. Заинтересованность может выражаться в получении макси¬мальной прибыли, минимальной себестоимости при заданной производительности, максимальной производительности при заданных затратах.

Современная экономическая наука существенно опирается на математи-ческое моделирование экономических процессов и пронизана различным математическим аппаратом, а применяющийся в ней математический язык позволяет более определенно и однозначно формулировать экономические факты и законы. Формализация основных особенностей функционирования экономических объектов позволяет оценить возможные последствия воздействия на них и использовать такие оценки в управлении.

Для решения задачи оптимального управления необходимо иметь в той или иной форме математическое описание оптимизируемого объекта и метод определения оптимальных управлений (решений). Для решения задачи опти-мального управления объектами используется метод математического моделирования.

Исследование экономических явлений математическими методами, в ча-стности в финансово-экономической сфере и бизнесе, помогает лицу, прини-мающему решение, произвести критический анализ ситуации и в результате более обоснованно и последовательно проводить определенную политику или стратегию поведения при решении сложных, комплексных проблем.

Целью данной курсовой работы является решение задач оптимизации методами линейного программирования на примере задачи о выборе оптимальных проектов для финансирования.

Данная цель обусловила решение в работе следующих задач:

1. Изучить понятие и методы линейного программирования.

2. Рассмотреть основные методы решения задач линейного программирования.

3. Построить математическую модель задачи о выборе оптимальных проектов для финансирования.

4. На основе решения принять управленческое решение и обосновать его.

5. Сделать выводы.

Предметом исследования курсовой работы является применение линей-ного программирования для решения задачи о выборе оптимальных проектов для финансирования в среде Microsoft Excel.

Объектом исследования выступает решение задачи о выборе оптималь-ных проектов для финансирования.

Методологической базой исследования являются общенаучные методы анализ, синтез, сравнение, аналогия, описательные методы и методы решения задач линейного программирования.

Информационной базой исследования выступают труды ученых, изу-чающих методы линейного программирования, учебная и специальная литература по методам исследования операций, ресурсы сети Интернет.

Структурно работа состоит из введения, теоретической части, практической части, заключения и списка использованных в работе источников.

1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Общая математическая формулировка задачи линейного программирования

На практике постоянно встречаются такие ситуации, когда достичь какого-то результата можно не одним, а многими различными способами. Естественно, при большом количестве решений выбирается наилучшее. Математически это обычно сводится к нахождению наибольшего и наименьшего значения некоторой функции. В зависимости от характера целевой функций и функций ограничения, различают разные виды математического программирования.

Линейное программирование (ЛП) – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т. е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования сводится широкий круг вопросов планирования экономических процессов, где ставится задача поиска наилучшего (оптимального) решения.

Линейность целевой функции и линейность условий связи варьируемых переменных являются основной особенностью задач линейного программирования.

Формулировка задачи линейного программирования

Естественной формой задачи линейного программирования является задача об определении максимума линейной целевой функции, обычно называемой линейной формой. Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных:

которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии,

,

при i = 1, 2, 3, . . . , m.

Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют «основной» или «стандартной» в линейном программировании.

Оптимальное решение задачи линейного программирования опре-деляется теми значениями параметров модели, которые они имели в момент ее формирования и построения. В реальной экономике значения параметров, формирующих модель, с течением времени или под воздействием каких-либо обстоятельств могут меняться. В связи с этим особый интерес представляют методы, позволяющие определить изменения в оптимальном решении, обусловленные изменениями значений параметров модели. Одним из источников таких методов является теория двойственности, результаты которой позволяют также производить экономический анализ оптимальных решений экономико-математических моделей.

Переменные двойственной задачи называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция исходной задачи формулируется на максимум, а це-левая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид , в задаче на минимум — вид ;

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица Ат в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональ-ных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства , соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.

Решая ЗЛП симплексным методом, одновременно решается двойственная ЗЛП. Переменные двойственной задачи называют объективно обусловленными оценками.

1.2. Методы решения задачи линейного программирования

В общем случае для решения задач линейного программирования используется симплекс-метод.

Сущность симплекс-метода состоит в том, что из исходного базиса переходят за один шаг в соседний с ним базис. Проверяют выполнение условий оптимальности в этом базисе. Если условие оптимальности не выполняется, то из этого базиса переходят в другой соседний с ним базис.

Алгоритм решения задачи симплекс-методом включает в себя однократно выполняемый 0-этап и повторяемый конечное число шагов 1-этап.

0-этап – нахождение первоначально допустимого базисного решения:

a) с помощью дополнительных неотрицательных переменных переходим к равенствам (каноническая форма задачи);

b) все переменные разбиваются на две группы: основные и неоснов-ные, при этом определитель матрицы, составленный из коэффициентов при основных переменных должен быть отличным от 0.

При выборе основных переменных на первом шаге не обязательно вы-числять этот определитель. Достаточно воспользоваться следующим правилом: на первом шаге в качестве основных переменных(если это можно) такие m переменных, каждая из которых входит только в одно из уравнений системы ограничений, при этом нет таких уравнений системы, в который не входит ни одна из этих переменных.

Если выбранные по этому правилу переменные имеют те же знаки, что и свободные члены в правых частях уравнений, то полученное базисное решение будет допустимо.

Пример исходной симплекс-таблицы для задачи ЛП:

Таблица 1

Симплекс-таблица

x1 x2 … xn-1 xn b

F -a0,1 -a0,2 … -a0,n-1 -a0,n -b0

xn+1 a1,1 a1,2 … a1,n-1 a1,n b1

xn+2 a2,1 a2,2 … a2,n-1 a2,n b2

… … … … … … …

xn+m am,1 am,2 … am,n-1 am,n bm

Нам известно, что x1, x2, xn − исходные переменные, xn+1, xn+2, xn+m − до-полнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные запи-саны в первый столбец симплекс-таблицы, а исходные в первую строку).

Алгоритм применения симплекс-метода

• Подготовительный этап

Приводим задачу ЛП к каноническому виду:

F=a0,1×1+a0,2×2+…a0,nxn +b0 → max

a1,1×1+a1,2×2+…a1,nxn+xn+1=b1

a2,1×1+a2,2×2+…a2,nxn+xn+2=b2

…………………………………

am,1×1+am,2×2+…am,nxn+xn+m=bm

В случае, если в исходной задаче необходимо найти минимум − знаки коэффициентов целевой функции F меняются на противоположные a0,n= −a0,n. Знаки коэффициентов ограничивающих условий со знаком «≥» так же меняются на противоположные. В случае, если условие содержит знак «≤» − коэффициенты запишутся без изменений.

• 0 этап

Составляем симплексную таблицу, соответствующую исходной задаче :

Таблица 2

Симплекс-таблица

x1 x2 … xn-1 xn b

F -a0,1 -a0,2 … -a0,n-1 -a0,n -b0

xn+1 a1,1 a1,2 … a1,n-1 a1,n b1

xn+2 a2,1 a2,2 … a2,n-1 a2,n b2

… … … … … … …

xn+m am,1 am,2 … am,n-1 am,n bm

• Шаг 1. Проверка на оптимальность

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных, то найдено допустимое оптимальное решение (решение, соответствующее одной из вершин многогранника условий). Тогда мы переходим к шагу 2.

Если в столбце свободных членов имеются отрицательные элементы, то выбираем среди них максимальный по модулю − он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l − он задает ведущий столбец − l и является ведущим элементом. Переменная, соответствующая ведущей строке исключа-ется из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс−таблицу согласно правилам (1).

Если среди свободных членов есть отрицательные элементы , а в соответствующей строке нет, то условия задачи несовместны и решений у нее нет.

Если после перерасчета в столбце свободных членов остались отрица-тельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

• Шаг 2. Проверка на неразрешимость

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность. Если среди элементов симплексной таблицы, находившихся в строке F (не беря в расчет элемент b0 — текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные элементы, то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0)

l − столбец, в котором находится этот элемент, будет ведущим. Для то-го, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.

k − строка, для которой это отношение минимально − ведущая. Элемент ak,l − ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис. Пересчитываем симплекс − табли-цу по формулам . Если в новой таблице после перерасчета в строке F остались отрицательные элементы, то переходим к шагу 2.

Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений за-дачи не ограничена − алгоритм завершает работу.

Если в строке F и в столбце свободных членов все элементы положи-тельные, то найдено оптимальное решение.

Правила преобразования симплекс-таблицы:

При составлении новой симплекс-таблицы в ней происходят следующие изменения (1):

• вместо базисной переменной xk записываем xl; вместо небазисной пе-ременной xl записываем xk;

• ведущий элемент заменяется на обратную величину ak,l’= 1/ak,l ;

• все элементы ведущего столбца (кроме ak,l) умножаются на −1/ak,l ;

• все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l ;

• оставшиеся элементы симплекс-таблицы преобразуются по формуле (2)

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого

базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

Геометрический (графический) метод

Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

Рис. 1. Система ограничений на плоскости

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

c1x1+c2x2 = а (3)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

Предположим надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имеющая наибольшую широту, т. е. точка через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).

Именно так и надо поступать при геометрическом решении задач линейного программирования . на многоугольнике решений следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а.

Линии уровня параллельны, так как их угловые коэффициенты опреде-ляются только соотношением между коэффициентами c1 и c2 и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели”, расположенные обычно под углом к осям координат.

Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении линии в другую сторону – только убывает.

Пусть имеются три линии уровня :

F=c1x1 + c2x2 = а1 (I)

F=c1x1 + c2x2 = а2 (II)

F=c1x1 + c2x2 = а3 (III)

Причём линия II заключена между линиями I и III. Тогда а1 < а2 < а3 и а1 > а2 > а3.

В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c1x1 + c2x2, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).

2. РАСЧЕТ ЗАДАЧИ О ВЫБОРЕ ОПТИМАЛЬНЫХ ПРОЕКТОВ ДЛЯ ФИНАНСИРОВАНИЯ

2.1. Вербальная постановка конкретной решаемой задачи

Рассмотрим задачу выбора оптимальных проектов для финансирования. Управляющему банка были представлены предложения о четырех проектах, претендующих на кредиты банка. При взвешивании этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов.

Доступная наличность банка, потребности проектов и прибыль по ним приведены в табл. 1.

Таблица 3

Доступная наличность банка, потребности проектов и прибыль по ним, в рассматриваемые периоды, тыс. долл.

Проект Период 1 Период 2 Период 3 Период 4 Прибыль

А 8 8 10 10 21

В 7 9 9 11 18

С 5 7 9 11 16

D 9 8 7 6 17,5

Ресурс банка 22 25 38 30

Какие проекты следует финансировать и какое количество наличности необходимо в течении каждого периода, если цель состоит в том, чтобы максимизировать прибыль?

2.2. Разработка экономико-математической модели задачи о выборе оптимальных проектов для финансирования

Построим экономико-математическую модель задачи, для этого введем необходимые обозначения:

Пусть xi – логические переменные, равные 1, если проект принимается и равные 0, если проект не принимается. Тогда суммарная потребность в наличности в данные период будет равна сумме произведений Xi на столбец финансовых затрат по каждому проекту в данный период.

В принятых обозначениях ограничения по ресурсам примут вид:

8×1 + 7×2 + 5×3 + 9×4 ≤ 22,

8×1 + 9×2 + 7×3 + 8×4 ≤ 25,

10×1 + 9×2 + 9×3 + 7×4 ≤ 38,

10×1 + 11×2 + 11×3 + 6×4 ≤ 30,

x1,x2,x3,x4 ≥ 1,

где X(x1,x2,x3,x4) – координаты точки X в R4 (4-мерном пространстве).

Так как неизвестные могут принимать только целые значения, то задача является задачей целочисленного программирования и

В этой модели целевая функция — это математическая запись критерия оптимальности «максимум прибыли от финансирования проекта» Целевая функция равна

F(x1,x2,x3,x4) = 21×1+18×2+16×3+17,5×4 → max.

Двойственная задача: пусть имеется спонсор, который захочет профинансировать те же проекты в тех же потребностях проектов в финансировании, при условии, что он получит от использования этих ресурсов большую прибыль, чем планируется банком.

Тогда целевая функция – это функция ограниченности ресурсов

X(x1,x2,x3,x4) = 22×1+25×2+38×3+30×4→min,

а ограничения примут вид:

8×1 + 8×2 + 10×3 + 10×4 ≥ 21,

7×1 + 9×2 + 9×3 + 11×4 ≥ 18,

5×1 + 7×2 + 9×3 + 11×4 ≥ 16,

9×1 + 8×2 + 7×3 + 6×4 ≥ 17,5.

Какие периоды спонсор станет финансировать и в каких пределах, чтобы его вложения были минимальны?

2.3. Решение поставленной задачи симплекс-методом

Решим прямую задачу линейного программирования строчечным сим-плекс-методом. Определим максимальное значение целевой функции

F(X) = 21×1+18×2+16×3+17,5×4

при следующих условиях ограничений:

8×1+7×2+5×3+9×4≤22

8×1+9×2+7×3+8×4≤25

10×1+9×2+9×3+7×4≤38

10×1+11×2+11×3+6×4≤30

Для построения первого опорного плана систему неравенств, приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

8×1 + 7×2 + 5×3 + 9×4 + 1×5 + 0x6 + 0x7 + 0x8 = 22

8×1 + 9×2 + 7×3 + 8×4 + 0x5 + 1×6 + 0x7 + 0x8 = 25

10×1 + 9×2 + 9×3 + 7×4 + 0x5 + 0x6 + 1×7 + 0x8 = 38

10×1 + 11×2 + 11×3 + 6×4 + 0x5 + 0x6 + 0x7 + 1×8 = 30

В качестве начальной допустимой базы можно взять B0 = (5, 6, 7, 8). Ей будет соответствовать следующая таблица.

Таблица 4

Симплекс-таблица с начальной допустимой базой

22 8 7 5 9 1 0 0 0

25 8 9 7 8 0 1 0 0

38 10 9 9 7 0 0 1 0

30 10 11 11 6 0 0 0 1

0 -21 -18 -16 -17.5 0 0 0 0

Переходим к основному алгоритму симплекс-метода.

Поскольку задача решается на максимум, то ведущий столбец выбирают по минимальному отрицательному числу в последней строке (максимальный по модулю).

max(-21,-18,-16,-17.5,0,0,0,0) = -21

В качестве ведущего выберем столбец, соответствующий переменной x1.

Таблица 5

Симплекс-таблица

22 8 7 5 9 1 0 0 0

25 8 9 7 8 0 1 0 0

38 10 9 9 7 0 0 1 0

30 10 11 11 6 0 0 0 1

0 -21 -18 -16 -17.5 0 0 0 0

Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей. Вместо переменной x5 в план войдет переменная x1.Разделим 1-ую строку на 8 и прибавим к последней строке, а затем вычтем из всех остальных строк.

Таким образом, очередной базис равен B0 = (1, 6, 7, 8).

max(0,0.38,-2.88,6.13,2.63,0,0,0) = -2.88

В качестве ведущего выберем столбец, соответствующий переменной x3.

Таблица 6

Симплекс-таблица

2.75 1 0.88 0.63 1.13 0.13 0 0 0

3 0 2 2 -1 -1 1 0 0

10.5 0 0.25 2.75 -4.25 -1.25 0 1 0

2.5 0 2.25 4.75 -5.25 -1.25 0 0 1

57.75 0 0.38 -2.88 6.13 2.63 0 0 0

Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:

Следовательно, 4-ая строка является ведущей. Вместо переменной x8 в план войдет переменная x3. Разделим 4-ую строку на 4.75 и прибавим к последней строке, а затем вычтем из всех остальных строк.

Таким образом, очередной базис равен B1 = (1, 6, 7, 3). Последняя строка не содержит отрицательных элементов. Найден оптимальный план.

Окончательный вариант таблицы:

Таблица 7

Симплекс-таблица с оптимальным планом

2.42 1 0.58 0 1.82 0.29 0 0 -0.13

1.95 0 1.05 0 1.21 -0.47 1 0 -0.42

9.05 0 -1.05 0 -1.21 -0.53 0 1 -0.58

0.53 0 0.47 1 -1.11 -0.26 0 0 0.21

59.26 0 1.74 0 2.95 1.87 0 0 0.61

Оптимальный план можно записать так:

x1 = 2.42

x6 = 1.95

x7 = 9.05

x3 = 0.53

F(x) = 21*2,42 + 16*0,53 = 59,26

2.4. Решение поставленной задачи с помощью средств EXСEL (надстройки «Поиск решения», «Анализ данных»)

Поиск решения — это надстройка EXCEL, которая позволяет решать оптимизационные задачи. После выбора команд Сервис  Поиск решения появится диалоговое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных параметра:

• Установить целевую ячейку

• Изменяя ячейки

• Ограничения

Сначала нужно заполнить поле «Установить целевую ячейку». Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же уста¬новить конкретное значение.

Второй важный параметр средства Поиск решения — это параметр «Изменяя ячейки». Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.

Третий параметр, который нужно вводить, для Поиска решения – это ограничения.

Для решения задачи необходимо:

• Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

• Ввести исходные данные.

• Ввести зависимость для целевой функции

• Ввести зависимости для ограничений.

• Запустить Поиск решений.

• Назначение целевой функции (установить целевую ячейку).

• Ввод ограничений.

• Ввод параметров для решения ЗЛП.

Начнем решение задачи в программе Excel. Введем переменные:

Таблица 8

 

Откроем диалоговое окно «Поиск решения». В нем зададим расположение целевой ячейки (в котором вычисляется значение целевой функции), вид оптимального решения (максимальное значение), расположение ячеек, которые будут изменяться при поиске решения (из них состоит вектор-строка оптимального плана), а также ограничения на изменяемые значения.

Рис. 3. Этап «Поиск решения»

Далее необходимо установить определённые параметры. В диалоговом окне «Поиск решения» выбираем «Параметры» и устанавливаем галочки на «Линейная модель» и «Неотрицательные значения».

Рис. 4. Этап «Параметры поиска решения»

После ввода необходимых данных нажмем кнопку «Выполнить» диалогового окна. В случае, если решение существует (и все данные введены верно), появляется сообщение:

Рис. 5. Этап «Результаты поиска решения»

После нажатия кнопки «ОК» в ячейках строки оптимального плана появляются значения его оптимальных элементов (оптимальный план); в ячейке целевой функции вычисляется соответствующее этому плану оптимальное значение целевой функции.

Таблица 11

Таблица результатов

Далее выводим на экран отчёт о результатах, отчёт об устойчивости, отчёт по пределам:

1) Отчет по результатам

 

Таблица 15

Таблица результатов

Так как двойственная задача решается на минимум, то отчетов по результатам у нас не будет.

2.5. Интерпретация результатов расчетов и выработка управленческого решения (с учетом решения двойственной задачи)

Таким образом, управляющему банка для получения максимальной прибыли равной 59,3 тыс. долл. целесообразно финансировать проекты А и С. Для финансирования данных проектов необходимо количество наличности в течение каждого периода:

В первом периоде необходимо 8 + 5 + 9 = 22 тыс. долл.

Во втором периоде необходимо 8 + 7 + 8 = 23 тыс. долл.

В третьем периоде необходимо 10 + 9 + 7 = 26 тыс. долл.

В четвертом периоде необходимо 10 + 11 + 6 = 27 тыс. долл.

Такими средствами банк располагает.

ЗАКЛЮЧЕНИЕ

Линейное программирование — это математическая теория, изучающая методы решения линейных экстремальных задач.

Оптимальному состоянию системы в задачах линейного программирования соответствует одна из вершин многогранника ограничений или оптимальное решение имеет бесчисленное множество точек, принадлежащих одной из граней многогранника ограничений.

Особый интерес представляют методы, позволяющие определить изменения в оптимальном решении, обусловленные изменениями значений параметров модели. Одним из источников таких методов является теория двойственности, результаты которой позволяют также производить эко-номический анализ оптимальных решений экономико-математических моделей.

Двумерная задачи линейного программирования может быть решена геометрически путём построения области допустимых управлений и построения линии уровня (постоянного значения линейной формы).

В общем случае для решения задач линейного программирования используется симплекс-метод.

Сущность симплекс-метода состоит в том, что из исходного базиса переходят за один шаг в соседний с ним базис. Проверяют выполнение условий оптимальности в этом базисе. Если условие оптимальности не выполняется, то из этого базиса переходят в другой соседний с ним базис.

При практической реализации симплекс-метода переход от одного базиса к другому и проверка базиса на оптимальность формализуются с использованием упрощающих приемов в форме симплекс-таблиц.

В работе решение задач линейного программирования рассмотрена на примере задачи выбора оптимальных проектов для финансирования. Управ-ляющему банка были представлены предложения о четырех проектах, претендующих на кредиты банка. При взвешивании этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов. Какие проекты следует финансировать и какое количество наличности необходимо в течении каждого периода, если цель состоит в том, чтобы максимизировать прибыль?

Была построена экономико-математическая модель данной задачи. Решение задачи представлено как в ручном просчете, так и с помощью инструмента Поиск решения программы Excel. Получены решения и проведена их экономическая интерпретация.

Управляющему банка для получения максимальной прибыли равной 54,5 тыс. долл. целесообразно финансировать проекты А, С и D. Для финансирования данных проектов необходимо количество наличности в течение каждого периода:

В первом периоде необходимо 8 + 5 + 9 = 22 тыс. долл.

Во втором периоде необходимо 8 + 7 + 8 = 23 тыс. долл.

В третьем периоде необходимо 10 + 9 + 7 = 26 тыс. долл.

В четвертом периоде необходимо 10 + 11 + 6 = 27 тыс. долл.

Такими средствами банк располагает.

Таким образом, средствами линейного программирования решается большое число экономических задач, требующих оптимизации при принятии правильного управленческого решения.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. — М.: ИНФРА-М, 2003. — 444 с.

2. Грызина Н.Ю., Мастяева И.Н., Семенихина О.Н. Математические методы исследования операций в экономике: Учебно-методический комплекс – М.: Изд-во ЕАОИ, 2008. – 204 с.

3. Калашникова Т.В. Исследование операций в экономике: учебное пособие / Т.В. Калашникова. – Томск: Изд-во Томского политехнического университета, 2007. – 92 с.

4. Кремер Н.Ш. Исследование операций в экономике. – М.: ЮНИТИ, 2010

5. Кривошеев, В.П. Теория оптимального управления экономическими системами: учебное пособие / В.П. Кривошеев. — Владивосток : Изд-во ВГУЭС, 2010. — 140 с.

6. Орлова И.В. Экономико-математические методы и модели. Выполнение расчетов в среде ЕХСЕL / Практикум: Учебное пособие для вузов. — М.:ЗАО Финстатинформ, 2000.-136 с.